package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         235,
		Discription: "二叉搜索树的最邻近祖先",
		Level:       1,
		Labels: map[string]int{
			"二叉树":   1,
			"二叉搜索树": 1,
			"递归":    1,
		},
	})
}

func LowestCommonAncestor(root, p, q *ds.TreeNode) *ds.TreeNode {
	if p.Val < root.Val && q.Val < root.Val {
		return LowestCommonAncestor(root.Left, p, q)
	}

	if p.Val > root.Val && q.Val > root.Val {
		return LowestCommonAncestor(root.Right, p, q)
	}

	//包含了pq一左一右，pq有一个等于root
	return root
}
